This is an open-label, multicenter, comparison study to determine the long-term safety and efficacy of liposomal dozorubicin alone or in combination with vincristine sulfate and bleomycin sulfate in the treatment of advanced AIDS-associated KS. Subjects will be enrolled and randomized to receive liposomal doxorubicin alone or in combination with vincristine sulfate and bleomycin sulfate. They will be stratified at randomization based on whether they are or are not currently receiving G-CSF of GM-CSF and by ACTG Oncology Committee prognostic variables. The status of KS lesions will be evaluated prior to the first administration of study medication, Immediately prior to every other cycle of treatment, and four weeks following the end of the last treatment cycle. Subjects will receive study treatment for up to 25 cycles or to a cumulative dose of 500mg/m2.